#include <memory>
#include <mutex>
#include <unordered_map>
#include <unordered_set>
#include <bits/stl_algo.h>

#include "CachePolicy.h"

namespace Cache
{
    template <typename K,typename V> class LfuCache;
    template <typename K,typename V> class LfuList;

    template <typename K,typename V>
    class LfuNode
    {
    private:
        K   _key;
        V   _value;
        int _freq;
        std::weak_ptr<LfuNode<K,V> > _prev;
        std::shared_ptr<LfuNode<K,V> > _next;

    public:
        LfuNode()
            :_freq()
        {

        }
        LfuNode(K key, V value)
            : _key(key), _value(value), _freq(1)
        {
        }

        LfuNode(K key, V value,int freq)
            : _key(key), _value(value), _freq(freq)
        {
        }

        K getKey() const {return _key;};
        V getValue() const {return _value;};
        void setKey(const K& key) {_key = key;};
        void setValue(const V& value) {_value = value;};

        friend class LfuList<K,V>;
        friend class LfuCache<K,V>;
    };

    template <typename K,typename V>
    class LfuList
    {
    public:
        using LfuNodePrt = std::shared_ptr<LfuNode<K,V> >;
        LfuNodePrt _head;
        LfuNodePrt _tail;
        int _freq;

    public:
        LfuList(int n) : _freq(n)
        {
            _head = std::make_shared<LfuNode<K,V> >();
            _tail = std::make_shared<LfuNode<K,V> >();
            _head->_next = _tail;
            _tail->_prev = _head;
        }

        bool isEmpty() const {return _head->_next == _tail;};

       void addNode(LfuNodePrt node)
       {
           if (!node ||!_head || !_tail)//为空
           {
               return ;
           }
           node->_prev = _tail->_prev;
           node->_next = _tail;
           _tail->_prev.lock()->_next = node;
           _tail->_prev = node;
       }

        void removeNode(LfuNodePrt node)
       {
           if (!node ||!_head || !_tail)
           {
               return;
           }
           if (node->_prev.expired() || !node->_next)
           {
               return;
           }
           auto prev = node->_prev.lock();
           prev->_next = node->_next;
           node->_next->_prev = prev;
           node->_next = nullptr;
       }

        LfuNodePrt getfirstNode() const {return _head->_next;};

        friend class LfuCache<K,V>;
    };

    template <typename K,typename V>
    class LfuCache : public CachePolicy<K,V>
    {
    public:
        using LfuNodePrt = std::shared_ptr<LfuNode<K,V> >;
        using LfuNodeListPrt = std::shared_ptr<LfuList<K,V> >;
        using LfuNodeMap = std::unordered_map<K,LfuNodePrt >;
        using LfuFreqMap = std::unordered_map<int,LfuNodeListPrt >;

        int         _capacity;       //缓存容量
        int         _minFreq;        //最小访问频次（用于寻找最小访问凭此节点）
        int         _maxAverageNum;  //最大平均访问频次
        int         _curAverageNum;  //当前平均访问频次
        int         _curTotalNum;    //前访问所有缓存次数总数
        LfuNodeMap  _nodeMap;
        LfuFreqMap  _freqMap;
        std::mutex  _mutex;

    public:
        LfuCache(int capacity,int maxAverageNum = 1000000)
            :_capacity(capacity)
            ,_minFreq(127)
            ,_maxAverageNum(maxAverageNum)
            ,_curAverageNum(0)
            ,_curTotalNum(0)
        {}

        ~LfuCache() override = default;

        void put(K key,V value) override
        {
            if (_capacity == 0)
            {
                return ;
            }
            std::lock_guard<std::mutex> lock(_mutex);
            auto it = _nodeMap.find(key);
            if (it != _nodeMap.end())
            {
                // 重置其value值
                it->second->_value = value;
                //刷新lfu缓存
                updateLfuCache(it->second, value);
            }
            else
            {
                insertLfuCache(key,value);
            }
        }

        bool get(K key, V& value) override
        {
            std::lock_guard<std::mutex> lock(_mutex);
            auto it = _nodeMap.find(key);
            if (it != _nodeMap.end())
            {
                value = it->second->_value;
                //刷新lfu缓存
                updateLfuCache(it->second, value);
                return true;
            }
            return false;
        }

        bool remove(K key,V& value) override
        {
            return true;
        }

        void updateLfuCache(LfuNodePrt node,V& value)
        {
            // 找到之后需要将其从低访问频次的链表中删除，并且添加到+1的访问频次链表中，
            // 访问频次+1, 然后把value值返回

            value = node->_value;
            //从访问频次的链表中删除
            removeFromFreqList(node);
            ++node->_freq;
            addToFreqList(node);
            /*
             如果当前node的访问频次如果等于minFreq+1，并且其前驱链表为空，则说明
             freqToFreqList_[node->freq - 1]链表因node的迁移已经空了，需要更新最小访问频次
             */
            if (node->_freq -1== _minFreq && _freqMap[node->_freq-1]->isEmpty())
            {
                _minFreq++;
            }
            // 总访问频次和当前平均访问频次都随之增加
            addFreqNum();
        }

        void insertLfuCache(K key,V value)
        {
            // 如果不在缓存中，则需要判断缓存是否已满
            if (_nodeMap.size() == _capacity)
            {
                // 缓存已满，删除最不常访问的结点，更新当前平均访问频次和总访问频次
                kickOut();
            }
            LfuNodePrt node = std::make_shared<LfuNode<K,V>>(key,value);
            _nodeMap[key] = node;
            addToFreqList(node);
            addFreqNum();
            _minFreq = std::min(_minFreq, 1);

        }

        void removeFromFreqList(LfuNodePrt node)
        {
            if (!node)
            {
                return ;
            }
            auto freq = node->_freq;
            _freqMap[freq]->removeNode(node);
        }

        void addToFreqList(LfuNodePrt node)
        {
            if (!node)
            {
                return;
            }
            // 添加进入相应的频次链表前需要判断该频次链表是否存在
            auto freq = node->_freq;
            if (_freqMap.find(freq) == _freqMap.end())
            {
                _freqMap[freq] = std::make_shared<LfuList<K,V>>(freq);
            }
            _freqMap[freq]->addNode(node);
        }

        void addFreqNum()
        {
            _curTotalNum++;
            if (_nodeMap.empty())
            {
                _curAverageNum = 0;
            }
            else
            {
                _curAverageNum =  _curTotalNum / _nodeMap.size();
            }

            if (_curAverageNum > _maxAverageNum)
            {
                handleOverMaxAverageNum();
            }
        }

        void handleOverMaxAverageNum()
        {
            if (_nodeMap.empty())
            {
                return;
            }
            // 当前平均访问频次已经超过了最大平均访问频次，所有结点的访问频次- (_maxAverageNum / 2)
            for (auto it = _nodeMap.begin(); it != _nodeMap.end(); ++it)
            {
                if (!it->second)
                {
                    continue;
                }

                LfuNodePrt  node = it->second;

                // 先从当前频率列表中移除
                removeFromFreqList(node);

                // 减少频率
                node->_freq -= _maxAverageNum/2;
                if (node->_freq < 1)
                {
                    node->_freq = 1;
                }

                addToFreqList(node);
            }

            // 更新最小频率
            updateMinFreq();
        }

        void kickOut()
        {
            LfuNodePrt node = _freqMap[_minFreq]->getfirstNode();
            removeFromFreqList(node);
            _nodeMap.erase(node->_key);
            decreaseFreqNum(node->_freq);
        }

        void decreaseFreqNum(int num)
        {
            _curTotalNum -= num;
            if (_nodeMap.empty())
            {
                _curAverageNum = 0;
            }
            else
            {
                _curAverageNum = _curTotalNum / _nodeMap.size();
            }
        }

        void updateMinFreq()
        {
            _minFreq = INT8_MAX;
            for (const auto& it : _freqMap)
            {
                if (it.second && !it.second->isEmpty())
                {
                    _minFreq = std::min(_minFreq, it.first);
                }
            }
            if (_minFreq == INT8_MAX)
            {
                _minFreq = 1;
            }
        }
    };
} // Cache